////////////////////////////////////////////////////////////////////////////////////////////////////
/// Copyright (c) 2009 - 2010 RacoonStudios
///
/// Permission is hereby granted, free of charge, to any person obtaining a copy of this
/// software and associated documentation files (the "Software"), to deal in the Software
/// without restriction, including without limitation the rights to use, copy, modify, merge,
/// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons
/// to whom the Software is furnished to do so, subject to the following conditions:
///
/// The above copyright notice and this permission notice shall be included in all copies or
/// substantial portions of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
/// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
/// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
/// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
/// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
/// DEALINGS IN THE SOFTWARE.
////////////////////////////////////////////////////////////////////////////////////////////////////

#pragma once
#ifndef simpletree_h__
#define simpletree_h__

#include "core/types.h"
#include "core/smrtptr.h"
#include "helper/array.h"

namespace Helper
{
	////////////////////////////////////////////////////////////////////////////////////////////////////
	/// \class	SimpleTree
	///
	/// \brief	This is just a SimpleTree. It contains a parent Node and could contain
	///			any amount of ChildNodes. For saving the childs we use an Array.
	///
	/// \author	khaos
	/// \date	14.12.2009
	////////////////////////////////////////////////////////////////////////////////////////////////////
	template<class T>
	class SimpleTree
	{
		public:

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \class	Node
			///
			/// \brief	The Node class. 
			///			Every Node contains an element and can handle any amount of ChildNodes.
			///
			/// \author	khaos
			/// \date	14.12.2009
			////////////////////////////////////////////////////////////////////////////////////////////////////
			class Node
			{
				public:

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	public: Node()
					///
					/// \brief	Constructor.
					///
					/// \author	khaos
					/// \date	05.01.2010
					////////////////////////////////////////////////////////////////////////////////////////////////////
					Node();

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	Node(const Node & parent, const T & val)
					///
					/// \brief	Constructor. 
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \param	[in]	parent	The parent Node.
					/// \param	[in]	val		The value this Node should contain.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					Node(const Node & parent, const T & val);

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	~Node()
					///
					/// \brief	Finaliser. 
					///
					/// \author	khaos
					/// \date	05.01.2010
					////////////////////////////////////////////////////////////////////////////////////////////////////
					~Node();




					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	const Node & operator[] (tIndex index) const
					///
					/// \brief	Casting operator. 
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \param	[in]	index	The position of the Node we want.
					///
					/// \return	Returns the Node at the specified position.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					const Node & operator [] (tIndex index) const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	Node & operator[] (tIndex index)
					///
					/// \brief	Casting operator. 
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \param	[in]	index	The position of the Node we want.
					///
					/// \return	Returns the Node at the specified position.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					Node & operator [] (tIndex index);




					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	void AddRef()
					///
					/// \brief	Adds a reference to this Node.
					///
					/// \author	khaos
					/// \date	05.01.2010
					////////////////////////////////////////////////////////////////////////////////////////////////////
					void AddRef();

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	void Release()
					///
					/// \brief	Releases this Node.
					///
					/// \author	khaos
					/// \date	05.01.2010
					////////////////////////////////////////////////////////////////////////////////////////////////////
					void Release();




					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	const Node & Child(tIndex index) const
					///
					/// \brief	Returns the ChildNode at the specified position.
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \param	[in]	index	The position of the ChildNode we want.
					///
					/// \return	Returns the ChildNode at the specified position.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					const Node & Child(tIndex index) const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	Node & Child(tIndex index)
					///
					/// \brief	Returns the ChildNode at the specified position.
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \param	[in]	index	The position of the ChildNode we want.
					///
					/// \return	Returns the ChildNode at the specified position.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					Node & Child(tIndex index);

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	bool HasParent() const
					///
					/// \brief	Determines if this Node has a parent Node. 
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \return	True if this Node has a parent Node, otherwise false.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					bool HasParent() const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	const Node & Parent() const
					///
					/// \brief	Returns the parent Node of this Node if there is one. 
					///			If there is none  we just reached the top level. Here we also
					///			allow reading access for this Node.
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \return	Returns the parent Node of this Node.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					const Node & Parent() const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	Node & Parent()
					///
					/// \brief	Returns the parent Node of this Node if there is one.
					///			If there is none we just reached the top level. Here we also
					///			allow reading as well as writing access for this Node.
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \return	Returns the parent Node of this Node.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					Node & Parent();




					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	void Clear()
					///
					/// \brief	Clears this Node.
					///			Here we call the Clear() procedure of the Array class. So every Node
					///			placed within this Node branch will be also deleted.
					///
					/// \author	khaos
					/// \date	05.01.2010
					////////////////////////////////////////////////////////////////////////////////////////////////////
					void Clear();

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	tSize Size() const
					///
					/// \brief	Returns the size of this Node.
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \return	Returns the size of this Node.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					tSize Size() const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	bool IsEmpty() const
					///
					/// \brief	Determines if this Child is empty.
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \return	True if the child Node is empty, otherwise false.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					bool IsEmpty() const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	Node & Front() const
					///
					/// \brief	Returns the first Node of the child branch.
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \return	The first child within the branch.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					Node & Front() const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	Node & Back() const
					///
					/// \brief	Returns the last Node of the child branch.
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \return	The last child within the branch.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					Node & Back() const;




					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	void Add(const T & val)
					///
					/// \brief	Adds an element to this child branch.
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \param	[in]	val	The element we want to add to this child branch.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					void Add(const T & val);

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	void Insert(tIndex index, const T & val)
					///
					/// \brief	Inserts the specified element at the specified position within the
					///			child branch.
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \param	[in]	index	The position we want the specified element to be placed.
					/// \param	[in]	val		The element itself.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					void Insert(tIndex index, const T & val);




					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	void Erase(tIndex index)
					///
					/// \brief	Erases the element at the specified index if available.
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \param	[in]	index	The position of the element we want to erase from the 
					///							child branch.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					void Erase(tIndex index);




					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	tIndex Find(const T & val) const
					///
					/// \brief	Searches for the specified element within this Node and all of its
					///			children.
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \param	[in]	val	The element we want to find.
					///
					/// \return	Returns the index if the element was found, otherwise InvalidIndex.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					tIndex Find(const T & val) const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	const T & Value() const
					///
					/// \brief	Returns the value of this Node.
					///			Note that you will only have reading access for this value.
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \return	This Node's value.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					const T & Value() const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	T & Value()
					///
					/// \brief	Returns the value of this Node.
					///			Note that you will have reading as well as writing access for this value.
					///
					/// \author	khaos
					/// \date	05.01.2010
					///
					/// \return	This Node's value.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					T & Value();

				protected:

				private:

					uint m_refCount;

					Node * m_parentNode;

					T m_value;

					Array<SmrtPtr<Node> > m_children;

			};

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	SimpleTree()
			///
			/// \brief	Default constructor. 
			///
			/// \author	khaos
			/// \date	05.01.2010
			////////////////////////////////////////////////////////////////////////////////////////////////////
			SimpleTree();

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	Node & Root()
			///
			/// \brief	Returns the root Node of this SimpleTree.
			///			Note that you will have reading as well as writing access for this Node.
			///
			/// \author	khaos
			/// \date	05.01.2010
			///
			/// \return	The root Node.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			Node & Root();

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	const Node & Root() const
			///
			/// \brief	Returns the root Node of this SimpleTree.
			///			Note that you will only have reading access for this Node.
			///
			/// \author	khaos
			/// \date	05.01.2010
			///
			/// \return	The root Node.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			const Node & Root() const;

		protected:

		private:

			Node m_root;

	};





	///
	template<class T>
	SimpleTree<T>::Node::Node():
	m_parentNode(0),
		m_refCount(0)
	{

	}


	///
	template<class T>
	SimpleTree<T>::Node::Node(const typename SimpleTree<T>::Node &parent, const T &val):
	m_parentNode(&parent),
		m_refCount(0),
		m_value(val)
	{

	}





	///
	template<class T>
	const typename SimpleTree<T>::Node & SimpleTree<T>::Node::operator [](tIndex index) const
	{
		return this->m_children[index];
	}


	///
	template<class T>
	typename SimpleTree<T>::Node & SimpleTree<T>::Node::operator [](tIndex index)
	{
		return this->m_children[index];
	}





	///
	template<class T>
	void SimpleTree<T>::Node::AddRef()
	{
		this->m_refCount++;
	}


	///
	template<class T>
	void SimpleTree<T>::Node::Release()
	{
		--this->m_refCount;

		if(this->m_refCount == 0)
			r_delete(this);
	}





	///
	template<class T>
	const typename SimpleTree<T>::Node & SimpleTree<T>::Node::Child(tIndex index) const 
	{
		return this->m_children[index];
	}


	///
	template<class T>
	typename SimpleTree<T>::Node & SimpleTree<T>::Node::Child(tIndex index)
	{
		return this->m_children[index];
	}


	///
	template<class T>
	bool SimpleTree<T>::Node::HasParent() const
	{
		return (this->m_parentNode != NULL);
	}


	///
	template<class T>
	const typename SimpleTree<T>::Node & SimpleTree<T>::Node::Parent() const 
	{
		return this->m_parentNode;
	}


	///
	template<class T>
	typename SimpleTree<T>::Node & SimpleTree<T>::Node::Parent()
	{
		return this->m_parentNode;
	}





	///
	template<class T>
	void SimpleTree<T>::Node::Clear()
	{
		this->m_children.Clear();
	}


	///
	template<class T>
	tSize SimpleTree<T>::Node::Size() const
	{
		return this->m_children.Size();
	}


	///
	template<class T>
	bool SimpleTree<T>::Node::IsEmpty() const
	{
		return this->m_children.IsEmpty();
	}


	///
	template<class T>
	typename SimpleTree<T>::Node & SimpleTree<T>::Node::Front() const
	{
		return this->m_children.Front();
	}


	///
	template<class T>
	typename SimpleTree<T>::Node & SimpleTree<T>::Node::Back() const
	{
		return this->m_children.Back();
	}






	///
	template<class T>
	void SimpleTree<T>::Node::Add(const T &val)
	{
		SmrtPtr<Node> temp = r_new(Node(*this, val));

		this->m_children.Add(temp);
	}


	///
	template<class T>
	void SimpleTree<T>::Node::Insert(tIndex index, const T &val)
	{
		SmrtPtr<Node> temp = r_new(Node(*this, val));

		this->m_children.InsertBefore(temp, index);
	}


	///
	template<class T>
	void SimpleTree<T>::Node::Erase(tIndex index)
	{
		this->m_children.EraseIndex(index);
	}





	///
	template<class T>
	tIndex SimpleTree<T>::Node::Find(const T &val) const
	{
		for(tIndex i = 0; i < this->m_children.Size(); i++)
		{
			if(this->m_children[i]->Value() == val)
				return i;
		}

		return InvalidIndex;
	}


	///
	template<class T>
	const T & SimpleTree<T>::Node::Value() const
	{
		return this->m_value;
	}


	///
	template<class T>
	T & SimpleTree<T>::Node::Value() 
	{
		return this->m_value;
	}





	///
	template<class T>
	SimpleTree<T>::SimpleTree()
	{

	}


	///
	template<class T>
	const typename SimpleTree<T>::Node & SimpleTree<T>::Root() const
	{
		return this->m_root;
	}


	///
	template<class T>
	typename SimpleTree<T>::Node & SimpleTree<T>::Root()
	{
		return this->m_root;
	}




}

#endif // simpletree_h__